import java.util.ArrayList;
import java.util.Random;

public class MyTest {
    public static void main(String[] args) {
        int count=10;
        MyPageGenerator mpg=new MyPageGenerator(count);
        int[] pages=mpg.getPages();
        int pageQuantity=3;
        MyFIFO myFIFO=new MyFIFO(pageQuantity);
        MyLRU myLRU=new MyLRU(pageQuantity);
        for(int i:pages){
            myFIFO.insert(i);
        }
        System.out.println("缺页次数为" + myFIFO.pageMissing + ",置换次数为" + myFIFO.pageDisplayed);
        for(int i:pages){
            myLRU.insert(i);
        }
        System.out.println("缺页次数为" + myLRU.pageMissing + ",置换次数为" + myLRU.pageDisplayed);
    }
}
class MyPageGenerator{
    int[] Pages;
    public MyPageGenerator(int count){
        if(count<0){
            throw new IllegalArgumentException();
        }
        Pages=new int[count];
        Random r=new Random();
        for(int i=0;i<count;i++){
            Pages[i]=r.nextInt(10);
        }
    }
    public int[] getPages(){
        //return Pages;
        return new int[]{7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
    }
}
abstract class  MyReplacementAlgorithm{
    int pageQuantity;//物理页面数
    int pageMissing;//缺页数
    int pageDisplayed;//置换次数

    public MyReplacementAlgorithm(int pageQuantity){
        this.pageQuantity=pageQuantity;
        pageMissing=0;
        pageDisplayed=pageMissing-pageQuantity;

    }

    public abstract void insert(int page);
    int[] pageList;//存放物理页面

}
class MyFIFO extends MyReplacementAlgorithm{
    public MyFIFO(int pageQuantity){
        super(pageQuantity);
        pageList= new int[pageQuantity];
        for(int i=0;i<pageList.length;i++){
            pageList[i]=-1;//用-1表示没有使用的物理页
        }
    }
    public void insert(int page){
        if(!isExist(page)) {
            pageMissing++;
            pageDisplayed++;
            for (int i = pageQuantity - 1; i > 0; i--)
                pageList[i] = pageList[i - 1];
            pageList[0] = page;
        }
        output();
    }

    /**
     * 判断pageList中是否存在相应的页面
     * @param page 需要判断的页面
     * @return 是否
     */
    public boolean isExist(int page){
        for(int i:pageList){
            if(i==page) return true;
        }
        return false;
    }
    public void output(){
        for(int i:pageList){
            System.out.print(i+"  ");
        }
        System.out.println();
    }
}
class MyLRU extends  MyReplacementAlgorithm{
    public MyLRU(int pageQuantity){
        super(pageQuantity);

    }
    ArrayList<Integer> pageList=new ArrayList<>();
    public void insert(int page) {
        if(!pageList.contains(page)){
            if(pageList.size()<pageQuantity){
                pageList.add(page);
            }else{
                pageList.set(0,page);
            }
            pageMissing++;
            pageDisplayed++;
        }else{
            for(int i=0;i<pageList.size();i++){
                if(pageList.get(i)==page){
                    pageList.remove(i);
                    pageList.add(page);
                    break;
                }
            }
        }
        output();
    }
    public void output(){
        for(int i:pageList){
            System.out.print(i+"    ");
        }
        System.out.println();
    }
}